Sequence variation within the non-pseudoautosomal region of the Y chromosome within and between the Hominidae can elucidate Y chromosome evolution and paternal human population history. The sequence of the coding region of the RPS4Y locus, a ribosomal protein gene, was determined in 4 non-human primate species and in 59 individuals from three human populations. Sequence analysis of RPS4Y in the Hominidae suggests that the RPS4Y protein is under relaxed functional selection compared to its highly conserved homolog, RPS4X, and predicts that the gene transposed to the Y chromosome approximately at the prosimian-simian divergence. Sequence variation at RPS4Y was detected both within and between human populations. One RPS4Y variant, C711T, appears to be the first common coding sequence polymorphism on the Y chromosome. The coalescent of human sequences (175,000 +/- 125,000 years) at this locus is similar to estimates derived from different Y loci and different human population samples. The ethnographic distribution of this Y chromosome substitution identifies a paternal lineage ancestral to Asian and Native American populations.